package 排序;

import java.util.*;
//1、交换类排序
//   冒泡排序：两两交换，最高的放末尾。O(n^2)。算法稳定。
//   快速排序：选队伍第一个人为基准，将队伍分成高矮两队，在小队伍中依旧这样。O(nlgn)。算法不稳定。
//2、选择类排序
//   选择排序：队伍后面的人，依次和队伍第一个人比较，将最小值放到队伍前面固定。O(n^2)。算法不稳定(如：5、8、5、2)。
//   堆排序：按照一个上级带两个下线的二叉树模型，推选出金字塔顶端的人，和金字塔底端的人交换位置后，固定金字塔底端的人位置，
//          继续整理金字塔。O(nlgn)。算法不稳定。
//3、插入排序
//   插入排序：默认把新来的插在队伍末尾，如果高度大于当前末尾值，位置正确，就不需要往队伍前面移动了，
//           否则，继续向队伍前面移动，直到符合递升高度美。稳定排序。
//   希尔排序：逐次将步长缩短，使两个相隔很远的数据能迅速交换---插入排序高效改进版。不稳定。
//4、归并排序
//   归：递归，并：合并。即先递归的分解数列直至单个元素(此时能视为有序数组)，再合并数列(从小到大合并)。稳定排序

//总结：一般只有两两相邻比较的排序算法，才是稳定的。

/**
 * Created by Administrator on 2017/8/4.
 */
public class eightSort {
    public static void main(String[] args) {
        //int[] arr=new int[]{1,8,3,4,0};
//        buddleSort(arr); //冒泡排序
//        System.out.println("冒泡排序："+ Arrays.toString(arr));
//        selectSort(arr);//选择排序
//        System.out.println("选择排序："+Arrays.toString(arr));
        //myQuickSort(arr,0,arr.length-1);
        //insert_sort(arr);
        //System.out.println("插入排序："+Arrays.toString(arr));

        //比较快速排序，堆排序，归并排序这三种时间复杂度为O(nlgn)的运行快慢
        //准备工作：产生4个完全一样，10_0000个元素的，元素值∈[0,1_0000)的随机数组
        int[][] arrs = createBigArray(4, 10_0000, 1_0000);
        //1、快速排序(最快)
        int[] arr1 = arrs[0];
        long startQuickSort = System.currentTimeMillis();  //产生一个当前的毫秒
        myQuickSort(arr1, 0, arr1.length - 1);
        long endQuickSort = System.currentTimeMillis();
        System.out.println("快速排序运行时间：" + (endQuickSort - startQuickSort));
        //2、堆排序
        int[] arr2 = arrs[1]; //和快速排序一样的大数组
        long startHeapSort = System.currentTimeMillis();
        MyHeapSort.insert_sort(arr2);
        long endHeapSort = System.currentTimeMillis();
        System.out.println("堆排序运行时间：" + (endHeapSort - startHeapSort));
        //3、归并排序(稳定)
        int[] arr3 = arrs[2];
        int temp[] = new int[arr3.length]; //开辟数组空间，用来存放每次临时的
        long startMergeSort = System.currentTimeMillis();
        MergeSort.mergesort(arr3, 0, arr3.length - 1, temp);
        long endMergeSort = System.currentTimeMillis();
        System.out.println("归并排序运行时间：" + (endMergeSort - startMergeSort));

        //顺便比较下时间复杂度为O(n^2)的排序算法：
        long startInsertSort = System.currentTimeMillis();
        //insert_sort(arrs[3]);  //插入排序
        shell_sort(arrs[3]);    //插入排序改进版：希尔排序(加速程度和步长的选择有关)
        long endInsertSort = System.currentTimeMillis();
        System.out.println("插入排序：" + (endInsertSort - startInsertSort));
        //参考结果(运行时间基本一致)：
//        快速排序运行时间：34   (单位：ms)
//        堆排序运行时间：34
//        归并排序运行时间：32
        //插入排序：5598
    }

    /**
     * @param element_num 需要比较的排序方法个数
     * @param element_num 随机数组的元素个数
     * @param maxNumber   元素的范围：[0,maxNumber)
     * @return 生成的随机数组
     */
    //要想比较三个O(nlgn)时间复杂度的算法，排序的数必须足够多
    public static int[][] createBigArray(int sort_method_num, int element_num, int maxNumber) {
        //1、产生随机数数组
        Random random = new Random(); //创建Random类对象
        int[][] ints = new int[sort_method_num][element_num]; //比较三种排序算法，所以需要三队完全一样的随机数
        for (int i = 0; i < element_num; i++) {
            ints[0][i] = random.nextInt(maxNumber); //[0,maxNumber)
        }
        System.out.println(Arrays.toString(ints[0])); //原始随机数组
        System.out.println(ints[0].length);
        //2、二维数组的索引为非0的一维数组，需要和上面随机数组一致，保证被排序的数组元素及位置一致
        for (int i = 1; i < sort_method_num; i++) {
            ints[i] = Arrays.copyOf(ints[0], element_num);
            System.out.println(Arrays.toString(ints[i])); //显示被复制的数组是否正确
        }
        return ints;
    }

    ///1、冒泡排序(相邻比较)
    //要想冒泡，必须相邻比较，将最小的数沉到最下面
    public static void buddleSort(int[] arr) {
        int temp = 0;//临时数据，用户交换数据的缓存
        for (int i = 0; i < arr.length - 1; i++) {//比较的次数
            for (int j = 0; j < arr.length - i - 1; j++) {//两两比较的第一个数
                if (arr[j] > arr[j + 1]) { //将大的数沉下去
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    //2、选择排序(和序列第一个比较)
    //选择排序，就是选择谁最小的问题。让最小的先排队买票。最小的放左边
    public static void selectSort(int[] arr) {
        int temp = 0;
        for (int i = 0; i < arr.length - 1; i++) { //队列中最小的
            for (int j = i + 1; j < arr.length; j++) { //后面还没有排好队的人群
                if (arr[i] > arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    //3、插入排序
//    一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
//    1、从第一个元素开始，该元素可以认为已经被排序
//    2、取出下一个元素，在已经排序的元素序列中从后向前扫描
//    3、如果该元素（已排序）大于新元素，将该元素移到下一位置
//    4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
//    5、将新元素插入到该位置后
//    6、重复步骤2~5
//    如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。
//    该算法可以认为是插入排序的一个变种，称为二分查找插入排序。
    public static void insert_sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) { //只需要插入arr.length-1次
            for (int j = i + 1; j > 0; j--) { //默认插在队伍末尾，如果大于前一个末尾值，位置正确，就不需要往队伍前面移动了
                if (arr[j - 1] <= arr[j]) break;
                //默认站在队伍末尾，但却又不是最高的，那么和前面的同学交换下位置，知道高度符合上升梯度
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }

        }
    }

    //shell(希尔)排序：插入排序更高效改进版。
    /*
    (1)希尔排序的实质就是分组插入排序，该方法又称缩小增量排序.
    (2)该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，
    然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为
    直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
    (3)希尔排序能加速，是因为使用了步长，能将部分元素先进行排序。

    以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例
    (1)第一次 gap = 10 / 2 = 5
    49   38   65   97   26   13   27   49   55   4
    1A                       1B
        2A                        2B
              3A                       3B
                   4A                       4B
                        5A                       5B
     1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素， 每次对同一组的数据进行直接插入排序。
     即分成了五组(49, 13) (38, 27) (65, 49)  (97, 55)  (26, 4)这样每组排序后就变成了
                 (13, 49)  (27, 38)  (49, 65)  (55, 97)  (4, 26)，下同。
     (2)第二次 gap = 5 / 2 = 2
     排序后
     13   27   49   55   4    49   38   65   97   26
     1A        1B        1C        1D        1E
           2A       2B        2C        2D        2E
     */
    public static void shell_sort(int[] arr) {
        int n = arr.length;
        int i, j, gap;
        for (gap = n / 2; gap > 0; gap /= 2) { //更新步长(每次为原来的一半，直到步长为0)
            for (i = gap; i < n; i++) { //从步长开始，将按步长分组的对应元素，进行插入排序
                    //gap=1时，希尔排序就变成插入排序了。但是因为元素已经部分排序好了，速度特别快！
                //插入排序代码
                for (j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap) { //队伍前面的人若比新来的高，交换位置
                    //两两交换位置
                    int temp = arr[j];
                    arr[j] = arr[j + gap];
                    arr[j + gap] = temp;
                }
            }
        }
        /*
        int gap = 1, i, j, len = arr.length;
        int temp;
        while (gap < len / 3)
            gap = gap * 3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
        for (; gap > 0; gap /= 3)
            for (i = gap; i < len; i++) {
                temp = arr[i];
                for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                    arr[j + gap] = arr[j];
                arr[j + gap] = temp;
            }
        */
    }

//    快速排序的原理：
//        选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。
//        一般选择序列的第一个元素作为基准值。
//    一次循环：
//        从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，
//    直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，
//    如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到  从前往后的比较索引>从后往前比较的索引，
//    结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。
//        接着分别比较左右两边的序列，重复上述的循环。

    public static void fastSort(int[] a, int low, int high) { //low:开始位置，high:结束位置
        int start = low;  //从前往后比较的索引(会依次变大)
        int end = high;   //从后往前比较的索引(会依次变小)
        int key = a[low]; //基准值

        while (end > start) { //从后往前比较的索引 > 从前往后比较的索引
            //从后往前比较(相等的值，则位置不变)
            while (end > start && a[end] >= key)  //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                end--;
            if (a[end] <= key) { //从后往前比较，小于基准值，则交换元素
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            //从前往后比较(相等的值，则位置不变)
            while (end > start && a[start] <= key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                start++;
            if (a[start] >= key) { //从前往后比，大于基准值，则放到后面
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
            //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
        }
        //递归
        if (start > low) fastSort(a, low, start - 1);//基准的左边序列。[序列左端索引，一次循环左索引-1]
        if (end < high) fastSort(a, end + 1, high);//基准的右边序列。[从一次循环右索引+1，序列右端索引]
    }

    //我的编写
    //基本原则：比基准点小的放其左边，大的放右边
//     * 以[2，3，1，5，0]数组为例，将以基准点分界的左右两边按大小分开的一组循环过程如下：
//     * 按照程序，初始start=0,end=4,基准点key=a[0]=2
//     * 4(end)>0(start),则
//     *     从后往前搜索：
//     *     while: 0(a[end=4])<2(key),比基准值小的出现在基准点右边，跳出循环，准备交换
//     *     if:    0(a[end=4])<2(key)，即比基准值小，交换到序列最前端(因为比基准值小的都在其左边)
//     *          交换后得：[0，3，1，5，2] (start=0,end=4,key=2)
//     *     从前往后搜索：
//     *     while: 0(a[start=0])<2(key),则start=start+1=1;
//     *            3(a[start=1])>2(key),比基准值大的出现在基准点左边，跳出循环，准备交换
//     *     if:    3(a[start=1])>2(key),交换序列两端索引元素(两端索引已更新)
//     *          交换后得：[0，2，1，5，3](start=1,end=4,key=2)
//     *
//     * 4(end)>1(start),则
//     *     从后往前搜索：
//     *     while: 3(a[end=4])>2(key),正常位置(从后往前搜索，发现比基准值大),end=end-1=3;
//     *            5(a[end=3])>2(key),正常位置(从后往前搜索，发现比基准值大),end=end-1=2;
//     *            1(a[end=2])<2(key),异常位置(从后往前搜索，发现比基准值小),跳出循环,准备交换
//     *    if:     1(a[end=2])<2(key),交换序列两端索引元素(两端索引已更新),
//     *          交换后得：[0，1，2，5，3](start=1,end=2,key=2)
//     *    从前往后搜索：
//     *    while: 1(a[start=0])<2(key),正常位置(从前往后搜索，发现比基准值小),start=start+1=2
//     *          end=start,说明以基准点为分界线的搜索已经搜索完毕
//     *          即基准点key=2，左边全是比2小的(虽然是无序的),右边全是比2大的(虽然是无序的)
//     *
//     * 接下来，对基准点两边，利用刚刚建立的函数递归调用即可！

    /**
     * @param arr       需要排序的数组
     * @param startInit 开始排序的索引位置(包含)
     * @param endInit   结束排序的索引位置(包含)
     */
    //一组循环后，目标排序：[比基准值小，基准值，比基准值大]
    public static void myQuickSort(int[] arr, int startInit, int endInit) {
        int start = startInit;
        int end = endInit;
        int key = arr[start];//基准值

        while (end > start) {
            //1、从后往前搜索
            while (end > start && arr[end] >= key) end--; //注意：对于和基准值相等的，不用动它，默认归队正确！
            //注意：单单一个条件arr[end]>=key控制不住循环，因为在小循环中，直接更改了大循环条件end,
            //      必须也将大循环条件再复制到小循环中，否则，可能出现end不受控制,导致索引越界。
            //发现乱归队的，将其换队(就比基准值大和比基准值小两个队伍)
            if (arr[end] < key) {
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }
            //2、从前往后搜索
            while (end > start && arr[start] <= key) start++;
            if (arr[start] > key) {
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }
        }
        //在一组循环结束后，排序结果为：[比基准值小，基准值，比基准值大]
        //这时，可采用递归法，对左右两个队伍，使用刚才的方案进行排序
        if (start > startInit) //start=startInit时，不需要排序。同时避免无限调用，导致死循环！
            myQuickSort(arr, startInit, start - 1);
        if (end < endInit) //end=endInit，不需要排序
            myQuickSort(arr, end + 1, endInit);
    }
}

//快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度*遍历次数N，
// 而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。
//扩展：N个节点的二叉树，最小深度计算
//假设二叉树为m层完美二叉树，则其节点个数肯定大于等于任意m层二叉树，即2^m-1 >= N ,即m>=lg(N+1)

//另一种关于时间复杂度的解释
//快速排序的基本思想是：每次从无序的序列中找出一个数作为中间点（可以把第一个数作为中间点），
//然后把小于中间点的数放在中间点的左边，把大于中间点的数放在中间点的右边；对以上过程重复
// log(n)次得到有序的序列。
// 快速排序的时间复杂性分析：排序的大体如下图所示，假设有1到8代表
// 要排序的数，快速排序会递归log（8）=3次，每次对n个数进行一次处理，所以他的时间复杂度为
// n*log(n)。所以排序问题的时间复杂度可以认为是对排序数据的总的操作次数。

//快速排序是二叉查找树（二叉查找树）的一个空间最优化版本。不是循序地把数据项插入到一个明确的树中，
//        而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。这两个算法完全地产生相同的比较次数，
//        但是顺序不同。对于排序算法的稳定性指标，原地分区版本的快速排序算法是不稳定的。其他变种是可以
//        通过牺牲性能和空间来维护稳定性的。
//快速排序的最直接竞争者是堆排序（Heapsort）。堆排序通常比快速排序稍微慢，但是最坏情况的运行时间总是O(n log n)。
//        快速排序是经常比较快，除了introsort变化版本外，仍然有最坏情况性能的机会。如果事先知道堆排序将会是需要
//        使用的，那么直接地使用堆排序比等待introsort再切换到它还要快。堆排序也拥有重要的特点，仅使用固定额外的
//        空间（堆排序是原地排序），而即使是最佳的快速排序变化版本也需要Θ(log n)的空间。然而，堆排序需要有效率
//        的随机存取才能变成可行。
//快速排序也与归并排序（Mergesort）竞争，这是另外一种递归排序算法，但有坏情况O(n log n)运行时间的优势。不像
//        快速排序或堆排序，归并排序是一个稳定排序，且可以轻易地被采用在链表（linked list）和存储在慢速访问
//        媒体上像是磁盘存储或网络连接存储的非常巨大数列。尽管快速排序可以被重新改写使用在炼串列上，但是它
//        通常会因为无法随机存取而导致差的基准选择。归并排序的主要缺点，是在最佳情况下需要Ω(n)额外的空间。

//最好情况下时间复杂度 O(n log n)：
// 在最好的情况，每次我们运行一次分区，我们会把一个数列分为两个几近相等的片段。这个意思就是每次递归调用处理一半大小的数列。
// 因此，在到达大小为一的数列前，我们只要作log n次嵌套的调用。这个意思就是调用树的深度是O(log n)。但是在同一层次结构的两个
// 程序调用中，不会处理到原来数列的相同部分；因此，程序调用的每一层次结构总共全部仅需要O(n)的时间（每个调用有某些共同的额外
// 耗费，但是因为在每一层次结构仅仅只有O(n)个调用，这些被归纳在O(n)系数中）。结果是这个算法仅需使用O(n log n)时间。

//最差情况下时间复杂度 O(n log n)：
//在最坏的情况是，两子数列拥有大各为1和n-1，且调用树（call tree）变成为一个n个嵌套（nested）调用的线性连串（chain）
//这与插入排序和选择排序有相同的关系式，以及它被解为T(n) = O(n2)。